package com.chenken;

/**
 *	求一段序列中最长连续子序列之和 
 *
 */
public class MaxSequence {
	
	/**
	 * dp(i)是以nums[i]结尾的最大连续子序列之和
	 * 	状态转移方程:
		  	如果dp[i-1] <= 0	表示前面的i-1个序列之和是个负数或0，那么第i个数字的最大子序列之和就是 dp[i] = nums[i]
			如果dp[i-1] > 0	表示前面的i-1个序列之和是整数	那么	dp[i] = dp[i-1] + nums[i]
	 *	 空间复杂度O(n)   时间复杂度O(n)
	 * @param nums
	 * @return
	 */
	public Integer maxSequence1(int[] nums) {
		if(nums == null || nums.length == 0) return 0;
		int[] dp = new int[nums.length];
		int max = nums[0];
		for(int i = 1;i < nums.length;i++) {
			if(dp[i-1] <= 0) {
				dp[i] = nums[i];
			}else {
				dp[i] = dp[i-1] + nums[i];
			}
			max = Math.max(max, dp[i]);
		}
		return max;
	}
	
	/**
	 * 	优化 	空间复杂度O(1)  时间复杂度O(n)
	 * @param nums
	 * @return
	 */
	public Integer maxSequence2(int[] nums) {
		if(nums == null || nums.length == 0) return 0;
		int dp = nums[0];
		int max = dp;
		for(int i = 1;i < nums.length;i++) {
			if(dp <= 0) {
				dp = nums[i];
			}else {
				dp = dp + nums[i];
			}
			max = Math.max(max,dp);
		}
		return max;
	}
	
	public static void main(String[] args) {
		int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
		System.out.println(new MaxSequence().maxSequence2(nums));
	}
	
}
